package LeetCode;

public class LC_450_DeleteNodeinaBST {

    public static void main(String[] args) {

    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public class Solution {
        TreeNode deleteNode(TreeNode root, int key) {
            if (root == null) return null;
            if (key < root.val)
                root.left = deleteNode(root.left, key);
            else if (key > root.val)
                root.right = deleteNode(root.right, key);
            else {
                if (root.left == null)
                    return root.right;
                else if (root.right == null)
                    return root.left;
                root.val = findMax(root.left).val;
                root.left = deleteNode(root.left, root.val);
            }
            return root;
        }

        private TreeNode findMax(TreeNode node) {
            while (node.right != null) node = node.right;
            return node;
        }

    }
}